﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0056_SearchRange : IAlgorithm
    {
        // 34. 在排序数组中查找元素的第一个和最后一个位置

        // 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
        // 如果数组中不存在目标值 target，返回[-1, -1]。

        // 进阶：
        //  你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

        // 提示：
        //  0 <= nums.length <= 10^5
        //  -10^9 <= nums[i] <= 10^9
        //  nums 是一个非递减数组
        //  -10^9 <= target <= 10^9

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 5, 7, 8, 8, 8, 10 };
            int target = 8;
            // 算法执行与打印
            var res = SearchRange(nums, target);
            Console.WriteLine($"[ {res[0]} , {res[1]} ]");
        }

        // 算法
        //  5, 7, 8, 8, 8, 10
        //  0, 1, 2, 3, 4, 5
        public int[] SearchRange(int[] nums, int target)
        {
            int leftIdx = BinarySearch(nums, target, true);
            int rightIdx = BinarySearch(nums, target, false) - 1;
            if (leftIdx <= rightIdx && rightIdx < nums.Length && nums[leftIdx] == target && nums[rightIdx] == target)
            {
                return new int[] { leftIdx, rightIdx };
            }
            return new int[] { -1, -1 };
        }
        public int BinarySearch(int[] nums, int target, bool lower)
        {
            int left = 0, right = nums.Length - 1, ans = nums.Length;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] > target || (lower && nums[mid] >= target))
                {
                    right = mid - 1;
                    ans = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return ans;
        }

    }
}
